/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: WHY
 * Date: 2022-11-07
 * Time: 19:14
 */
//反转链表
import java.util.*;
public class Solution {
    public ListNode ReverseList(ListNode head) {
        //采用入栈出栈的方式
        //1.首先创建一个栈，并且将元素都放入栈中
        Stack<ListNode> stack=new Stack<>();
        while(head!=null){
            stack.push(head);
            head=head.next;
        }
        if(stack.isEmpty()){
            return null;
        }
        ListNode node=stack.pop();
        //将栈顶元素设为头结点
        ListNode ret=node;
        //出栈
        while(!stack.isEmpty()){
            ListNode tmpNode=stack.pop();
            node.next=tmpNode;
            node=node.next;
        }
        node.next=null;//将头结点下一个元素置为空，防止构成环
        return ret;



    }
}
